The present invention relates to an image describing apparatus capable of describing a coupling area (hereinbelow referred to as an area) of an image in a graphic command of polygonal or arcuate shape, describing a boundary of the areas in a primitive of a straight or linear line or circular arc, and extracting the profile of two-dimensional pattern of a character or a graphic figure.
A conventional apparatus of this type has been heretofore proposed in an article entitled. "Some Experiments in Image Vectorization", Jimenez et al, published in IBM Journal Research and Development, Volume 26, Number 6, pages 724-734, November 1983.
FIG. 1 is a diagram of the system construction of a conventional apparatus, FIG. 2 is a flow chart showing the sequence of operations, and FIGS. 3(a) and 3(b) are tables explaining the rows of profile points. In FIG. 1, reference numeral 20 designates an image input device, numeral 21 designates an image memory, numeral 22 designates a Central Processing Unit (CPU), numeral 23 designates a processing program, numeral 24 designates a working memory, numeral 25 designates an extraction area memory, numeral 28 designates an encoded data memory, and numeral 9 designates a Cathode Ray Tube (CRT) display. In FIG. 2, reference numeral 11 designates input image data, numeral 303 designates binary image data, numeral 304 designates profile point row data, and numeral 15B designates encoded data.
In the conventional example shown in FIG. 2, the CPU 22 reads the multivalue or multicolor input image data 11 stored in the image memory 21 via the image input device 20, separates it into predetermined tones or color units in accordance with the processing program 23, and converts it into binary image data 303 for the respective units in step 300. For example, the CPU inputs the image data 11 with each picture element represented by 8 bits denoting its gray level and encodes each picture element, using two predetermined threshold values to separate the picture elements into three sets representing two different color units, by a single bit value (e.g., representing one color unit with "0" and the other with "1").
Then, in step 301, the CPU extracts the profile points of the area (for example, the area having the value "1") to be extracted from the binary image data 303 obtained in step 300 to represent the boundary of that area. Here, the profile point row means a set of the picture elements disposed at the outermost side of the area of the picture elements belonging to this area as listed in FIG. 3. A method of extracting the profile point row of the binary image data is well known and carried out through the use of a matrix of 2.times.2 or 3.times.3.
The CPU inputs the profile point row data 304 obtained in step 301, approximates the profile point row data in a linear primitive, and forms encoded data 15 described in a polygonal graphic command in the respective areas in step 302. This approximation is carried out in the coordinates of the vertices of the polygonal shape within a predetermined allowable tolerance. A number of methods have been heretofore devices, for example, in "Image Processing by Computer", issued by Sanpo Shuppan, written by Takeshi Yasuiin et al, Electronic Scientific Series 84, pages 95-96.
It is necessary in this conventional example to describe a curve in the shape of a polygon having a number of vertices. To reduce the allowable error of the approximation when it is desired to approximate a curve, the number of vertices must be large.
FIG. 4 is a view of the system construction of another convention example, FIG. 5 is a flow chart showing the sequence of operations to be performed, and FIGS. 6(a) and 6(b) are tables outlining the profile of the area. In FIG. 4, reference number 21A designates an image input device, numeral 22A designates an image memory, numeral 23A designates a processing program, numeral 24A designates a CPU, numeral 25A designates a working memory, numeral 26A designates an extraction area memory, numeral 28A designates an image description memory, and numeral 7A designates a CRT display. In FIG. 5, reference numeral 9A designates input image data, numeral 215A designates binary image designates input image data, numeral 215A designates binary image data, numeral 216A designates profile point row data, and numeral 12A designates image description data.
In the conventional example shown in FIG. 5, the CPU 24A reads the multivalue or multicolor image data 9A stored in the image memory 22A via the image input device 21A, separates it into predetermined tones or color units in accordance with the processing program 23A, and converts it into binary image data 215A for the respective units in step 211A. For example, the CPU 24A inputs the image data 9A with each picture element represented by 8 bits denoting its gray level and encodes each picture element, using two predetermined threshold values to separate the picture elements into three sets representing two different color units, by a single bit value (e.g., representing one color unit with "0" and the other with "1").
Then, in step 212A, the CPU 24A extracts the profile point row of the area (for example, the area having the value "1") to be extracted from the binary image data 215A obtained in step 211A to represent the boundary of that area. Here, the profile point row means a set of the picture elements (the profile point row of the outside) disposed at the outermost side of the area of the picture elements belonging to the area and a set of the picture elements (the profile point row of the inside) surrounding an island when the area has an island. A method of extracting the profile point row of the binary image data is well known and carried out through the use of a matrix of 2.times.2 or 3.times.3.
The CPU 24A inputs the profile point row data 216A obtained in step 212A and describes the image by approximating the profile point row in a linear primitive in step 213A. This approximation is carried out by approximating the profile point row in the coordinates of the vertices of a polygonal line within a predetermined allowable error. A number of methods have been heretofore devices, for example in the article entitled "Curve Fitting as a Pattern Recognition Problem", Theo Pavlidis, IEEE Proc. 6th Int. Conf. Pattern Recogn., pages 853-859, 1982. In the construction of the image description data 12A thus formed, the areas are formed in the tones or color units and described by one approximate profile corresponding to the outside profile and a number of approximate profiles as inside profiles corresponding to the number of islands.
In the conventional example described above, since the area containing islands is described by both the approximate profile corresponding to the outside profile and also by the approximate profile corresponding to the inside profile, and the area representing the island is described by the approximate profile corresponding to the outside profile of the island adjacent to the inside profile of the area containing island, the boundary of the area representing the island is defined by two redundant profiles.
FIG. 7 is a view of the system construction of still another convention example, FIG. 8 is a flow chart showing the sequence of operations in the example, and FIGS. 9(a) through 9(c) explain the problems of the conventional example. In FIG. 7, reference number 21B designates an image input device, numeral 22B designates an image memory, numeral 23B designates a processing program, numeral 24B designates a CPU, numeral 25B designates an extraction boundary memory, numeral 27B designates an image description memory, and number 7B designates a CRT display.
In the conventional example shown in FIG. 8, the CPU 24B reads the multivalue or multicolor image data 9B stored in the image memory 22B via the image input device 21B, separates it into predetermined tones or color units in accordance with the processing program 23B, and converts it into binary image data 215B for the respective units in step 211B. For example, the CPU inputs the image data 9B with each picture element represented by 8 bits denoting its gray level and encodes each picture element, using two predetermined threshold values to separate the picture elements into two sets representing two different colors units, by a single bit value (e.g., representing one color unit with "0" and the other with "1").
Then, in step 212B, the CPU 24B extracts the profile point row of coupling areas (hereinbelow referred to as areas) of the binary image data 215B obtained in step 211B to represent the boundaries of those areas. Here, the profile point row means a set of the picture elements disposed at the outermost side of the area of the picture elements belonging to the area. For example, in the case of the binary image shown in FIG. 5(a), the profile point row of the areas 1 and 2 in FIGS. 9 becomes a set of picture elements as shown in FIG. 53(b). A method of extracting the profile point row of the binary image data is well known and carried out through the use of a matrix of 2.times.2 or 3.times.3.
The CPU 24b inputs the data 216B of the profile point row obtained in step 212B and approximates the profile point row in a linear primitive. This approximation is carried out by approximating the profile point row in the coordinates of the vertices of a polygonal line within the predetermined allowable error.
In the conventional example described above, a linear approximation is carried out for the profile point row units of the respective areas, and the relation to the other profile point row contacted as a boundary (FIG. 53(c)) has not been entirely considered. Generally, according to a method of linearly approximating a point row if the points of starting the approximations are different for the same point row, different approximation results are obtained. Therefore, if the linear approximation for the point rows start from point Q.sub.3 for the area 1 and from point Q.sub.4 for the area 2, the approximation results shown in FIGS. 9(b) and 9(c) are obtained. Thus, the approximation is not carried out by the same polygonal line between the points Q.sub.1 and Q.sub.2 corresponding to the adjacent boundaries of areas 1 and 2. For example, in the case of indicating the approximation result, a gap is formed in the vicinity of the boundary between the areas 1 and 2.
The conventional technique for extracting the profile of a character or two-dimensional graphic pattern is, for example, disclosed in detail in the article entitled "An Improved Segmentation and Coding Algorithm for Binary and Nonbinary Images", Per-Erik Danielsson, IBM Journal Research and Development, Volume 26, Number 6, pages 698-707, November 1982. In order to extract the profile of such a two-dimensional pattern, a conventional apparatus as shown in FIG. 10 is employed. In FIG. 10, reference number 141C designates image data memory means, numeral 142CA designates raster scan type unextracted area detecting means, numeral 143C designates island profile tracing means, numeral 144C designates peripheral area label describing means, numeral 145C designates area profile tracing means, numeral 146C designates extracted area label describing means, numeral 147C designates adjacent unextracted area flag describing means, and numeral 148C designates profile information memory means. Here, the term "area" means a set of coupled picture elements having the same value. An island is an area surrounded by another area as shown in FIG. 71(a). For example, in FIG. 71(a), the area B is the island of the area A, and the areas C, D, and E form the islands of the area A. Further, a boundary line is a line for isolating between a picture element contained in a certain area and another picture element adjacent to the first picture element and contained in another area and is, as shown in FIG. 71(b), 122C which is the boundary line between areas E and F. The profile of an area (or island) means to a description of the shape of that area (or island). For example, in FIG. 71(b), the point row 121C of the picture elements adjacent to the outside of the boundary line 122c, the point row 123c of the picture elements adjacent to the inside of the boundary line 122C or the boundary line 122c between the areas E and F are considered as the profile of the area E and may be used to reproduce the shape of that area.
In the conventional apparatus, a two-dimensional pattern for extracting the profile is first stored in the image data memory means 141C, and the picture element contained in the unextracted area is discovered by raster scanning the abovementioned pattern in the unextracted area detecting means 142C. Then, the unextracted area containing the discovered picture element is judged as to whether it forms an unextracted island of the area scanned immediately before the discover of that picture element or that it is adjacent to another area scanned immediately before the discovery of that picture element, and the two adjacent areas are obtained within the same island. In the former case, the profile of the island containing the area containing the picture element is extracted by the island profile tracing means 143C. At this time, the label name of the area scanned immediately before the discovery of the island is described on the picture element adjacent to the boundary line for forming the profile of the island by the peripheral area label describing means 144C. The profile point row of the obtained island is stored in the profile information memory means 148C. In the latter case, the profile of the area having the discovered image is extracted in the area profile tracing means 145C. At this time, the label name of the area is described on the picture element at the outermost side of that area by the extracted area label describing means 146C. If the picture element adjacent to the boundary line for forming the profile in the scanning direction side is disposed at the outside of the area during the tracing and the label name is not described, the unextracted area flag is attached to the picture element. The raster scanning is assumed to be conducted in the direction shown in FIG. 72, and the operation of the conventional apparatus will be described in detail with reference to the flow chart in FIG. 11 and the pattern examples of FIGS. 12 to 14.
In the pattern in FIG. 12, the label name of the area having a value "0" containing the picture element (1, 1) is A. When a raster is scanned from (1, 1) in the direction specified by FIG. 72, the point (hereinbelow referred to as a varying point) varying the value of the adjacent picture element in the direction of the raster is discovered in the coordinates (2, 3), the point advances in step 1511C in FIG. 11 and traces the island profile. At this time, since the area scanned immediately before the varying point has been discovered, i.e., the area containing the point (1, 3) is A, the label name A is described on the picture element of the outside of the boundary line for forming the profile of the island, as shown in FIG. 11 in step 1512C. Assuming that the profile information is extracted as the point row data of the boundary line represented by a chain code as shown in FIG. 65 in the displacing direction of the boundary line between the areas, the chain 1 in FIG. 13, i.e., the starting point (2, 3), and the displacement, 0, 0, 0, 0, 0, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, are obtained as the profile information of the island by this tracing. In addition, an unextracted area flag is attached as a mark "o" to the picture element in the island adjacent to the boundary line for forming the profile of the island in the scanning direction side in step 1514C at the island profile tracing time.
When the tracing of the profile of the island is finished and the raster scanning is then started, the picture element (2, 3) attached with the unextracted area flag is immediately discovered, and the profile tracing of a new area containing the varying point (2, 3) is carried out in steps 1504C to 1509C. Assuming that the label name of this new area is B, the label name B is described on the picture element of the profile of the inside of the area of the value "1" containing the picture element (2, 3) in step 1505C (FIG. 14). The unextracted area flag is so described as to attach the mark "o" to the picture elements not described with the label name of the picture elements in the area outside of the boundary line for forming the profile of the area B, i.e., (5, 5), (5, 6), 5, 7). By this area profile tracing, a chain 2 of FIG. 14, i.e., the starting point (2, 3), and the displacement 0, 0, 0, 0, 0, 3, 3, 2, 2, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1 are obtained as the profile of the area B. At this time, the fact that the area B forms the island of the area A and that the profile of the island is the chain 1 is recorded in the profile information memory means 148C. When the profile tracing of the area B is finished, the raster scanning is again started from the picture element (2, 3). Then the varying point is discovered in the picture element (8, 4). The island profile tracing is then conducted, and the profile chain 3 of the island, i.e., the starting point (8, 4), and the displacement 0, 0, 3, 3, 2, 2, 1, 1 are obtained. At this time, the label name or the unextracted area flag is described as shown in FIG. 14 in the pattern. Then, when the area profile is traced from the picture element (8, 4), the profile chain 4 of the area C of a value "3", i.e., the starting point (8, 4), and the displacement 0, 0, 3, 3, 2, 2, 1, 1 are obtained. Then, the fact that the profile of the island in the area for forming the island in the area A of the area C is chain 3 is stored in the profile information memory means (148C). When the raster is again scanned, the picture element with the unextracted area flag is discovered in the picture element (5, 5). The unextracted area flag indicates that the area containing the picture element is scanned immediately before the area, i.e., disposed adjacent to the same island as the area B. Then, the profile of the area containing the picture element is traced. Thus, the chain 5, i.e., the starting point (5, 5) and the displacement 0, 0, 3, 3, 3, 2, 2, 1, 1, 1, are obtained as the profile of the area D of a value "2". Further, the fact that the areas B and D are connected in the same island is stored in the profile information memory means 148C.
As described above, there are obtained point row data of the boundary line for forming the profiles of the areas A, B, C, and D from the two-dimensional pattern in FIG. 12 and a topological connecting relation between the areas as the profile information by the above process.
As also described above, there is a problem in the conventional apparatus in that, since the profile point rows of the areas are extracted and the profile point row is approximated in a linear primitive to describe the area in a polygonal shape, if components of a curve, such as a circular arc, are contained in the profile line of the extracted area, the curve must be described in the polygonal shape having a large number of vertices, and the quantity of data for describing the image increases.